package com.njupt.Tree;

import java.util.Deque;
import java.util.LinkedList;

/**
 * @Author: wujiaming
 * @CreateTime: 2024/11/29 10:40
 * @Description: 404. 左叶子之和
 * @Version: 1.0
 */


public class SumOfLeftLeaves {


    private static int sum = 0;
    /**
     * 非递归算法
     * @param root
     * @return
     */
    public int sumOfLeftLeaves1(TreeNode root) {
        Deque<TreeNode> stack = new LinkedList<>();
        TreeNode cur = root;
        int sum = 0;
        while(cur != null || !stack.isEmpty()){
            if(cur != null){
                //访问根节点
                if(cur.left != null && (cur.left.left==null && cur.left.right ==null)){
                    sum += cur.left.val;
                }
                stack.push(cur);
                cur = cur.left;
            }else {
                cur = stack.pop();
                cur = cur.right;
            }
        }
        return sum;
    }

    /**
     * 后续遍历递归算法
     * @param root
     * @return
     */
    public  int sumOfLeftLeaves2(TreeNode root) {
        //递归终止的条件
        if(root == null){
            return 0;
        }

        //后续遍历
        int left = sumOfLeftLeaves(root.left); //左
        if(root.left != null && (root.left.left == null && root.left.right == null)){
            left = root.left.val;
        }
        int right = sumOfLeftLeaves(root.right);//右


        return left + right;                    //中
    }


    /**
     * 使用静态变量保存中间的结果
     * @param root
     * @return
     */
    public  int sumOfLeftLeaves(TreeNode root) {

        if(root == null){
            return 0;
        }
        if(root.left != null && (root.left.left == null && root.left.right == null)){
            sum += root.left.val;
        }
        sumOfLeftLeaves(root.left);
        sumOfLeftLeaves(root.right);

        return sum;
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(9);
        root.right = new TreeNode(20);
        root.right.left = new TreeNode(15);
        root.right.right = new TreeNode(7);
        SumOfLeftLeaves test = new SumOfLeftLeaves();
        System.out.println(test.sumOfLeftLeaves2(root));
    }
}
